package com.example.leetdemo.process;

import org.springframework.util.CollectionUtils;

import java.util.*;

public class Solution870 {

    // leetcode不认SortMap
    public int[] advantageCount1(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        int[] result = new int[nums1.length];
        TreeMap<Integer, Integer> sortedMap = new TreeMap<>();

        for (int i = 0; i < nums1.length; i++) {
            sortedMap.put(nums1[i], sortedMap.getOrDefault(nums1[i], 0) + 1);
        }
        for (int i = 0; i < nums2.length; i++) {
            SortedMap<Integer, Integer> tailMap = sortedMap.tailMap(nums2[i]);
            if (tailMap.size() == 0) {
                result[i] = sortedMap.firstKey();
                sortedMap.put(sortedMap.firstKey(), sortedMap.get(sortedMap.firstKey()) - 1);
            } else {
                result[i] = tailMap.firstKey();
                sortedMap.put(tailMap.firstKey(), sortedMap.get(tailMap.firstKey()) - 1);
            }
            if (sortedMap.get(result[i]) <= 0) {
                sortedMap.remove(result[i]);
            }
        }
        return result;
    }

    public int[] advantageCount(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        int[] result = new int[nums1.length];
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < nums1.length; i++) {
            deque.addLast(nums1[i]);
        }
        for (int i = 0; i < nums2.length; i++) {
            if (deque.peekLast() <= nums2[i]) {
                result[i] = deque.pollFirst();
            } else {
                Stack<Integer> stack = new Stack<>();
                while (deque.peekFirst() != null && deque.peekFirst() < nums2[i]) {
                    stack.push(deque.pollFirst());
                }
                result[i] = deque.pollFirst();
                while (stack.size() > 0) {
                    deque.addFirst(stack.pop());
                }
            }
        }
        return result;
    }


    public static void main(String[] args) {
        Solution870 solution870 = new Solution870();
        int[] answer = solution870.advantageCount(
                new int[] {12,24,8,32} , new int[] {13,25,32,11});

        System.err.println(answer.length);
    }
}
